"""
Object for manipulation of Rauzy Graphs.

    We define here three objects
        ShapeOfRauzyGraph: The most general. It is a weighted type of graphs.
        The weight has to be thought as a length (in particular it must have an
        .__add__ method and an .__iadd__ method or a coercion mechanism from the
        integers).

        DerivedShapeOfRauzyGraph: In this type of graph each edge has a state.
        States values can be :
           0  : consider the edge not here (but could go to 1)
           1  : consider the edge here (but could go to 0)
          -1 : immutable edge which is here.
        A MultiDiGraphX must be connected (just considering 1 and -1 state
        edges). Moreover, the class provide some graph method adapted to our
        context.

        SimplifieShapeOfRauzyGraph: This type is the same as above, except
        that all its vertices are specials (valence > 2). There is a special
        method for this type call derive which return a WeightedMultiDiGraphX
        corresponding to the line graph of this.

    TODO:
        The substitution induced on n-segments.
"""

try :
    import networkx as nx
except ImportError :
    raise ImportError, "The library need networkx"

if nx.__version__ < '1.0' :
    raise DeprecationWarning("networkx version must be >= 1.0")


from simplex import SimplexOfLengths

def dict_find_key(dic, val):
    """
    return the key of dictionary dic given the value
    """
    return [k for k, v in dic.iteritems() if v == val][0]

def dict_rename_keys(dic, map):
    """
    map old_name -> new_name (bijective! not renamed keys won't be present)
    """
    new_dic = {}
    for key in map.keys():
        if dic.has_key(key):
            new_dic[map[key]] = dic[key]
            
    return new_dic


class RauzyGraphShape(nx.MultiDiGraph):
    """
    Shape of graph.
    """

    def __init__(self, d=None):
        """
        The initialization must be done with a dictionary in the following form
        {1 : [(2,4),(3,5)], 2 : [(2,2),(3,5),(4,1)], 3 : [(2,3)], 4 :
        [(2,1),(3,1)]}
        where the keys are the vertices and the list correspond to neighbors
        with multiplicity.
        defines states of edges \in {don't touch = -1,not there = 0,is there = 1}
        using set_state
        """
        super(nx.MultiDiGraph, self).__init__()

        if d == None: d = {}
        self.__lengths = {}

        for vertex, list_successor in d.iteritems():
            for successor,multiplicity in list_successor:
                for i in range(multiplicity):
                    self.add_edge(vertex, successor, i, 0)

    def __str__(self):
        """
        String representation of self
        """
        s = "Printing out graph in format: (vertex from) --( length)--> (vertex to), label \n"
        for edge in self.edges(data = True) :
            s += str(edge[0]) + " --(%2d)--> " %(self.get_length(edge)) + str(edge[1]) + ", " + str(edge[2]) + "\n"
            
        return s

    def add_edge(self, node1, node2, label, length=0):
        """
        Add an edge to the RauzyGraphShape.

        INPUT:
            node1 -- the name of a node
            node2 -- the name of a node
            label -- the label of the edge
            length -- a length
        """
        super(RauzyGraphShape, self).add_edge(node1,node2,label)
        self.set_length((node1, node2, label), length)

    def add_edge_with_automatic_label(self, node1, node2, length=0):
        """
        Add an edge to the RauzyGraphShape choosing automatically the number of
        the edge depending on what is present.
        """
        if not self[node1].has_key(node2): label = 0
        else: label = max(self[node1][node2]) + 1
        self.add_edge(node1, node2, label, length)
        return label

    def delete_edge_and_length(self, edge):
        """
        Deletion of an edge of the graph.

        INPUT:
            edge - a 3-tuple corresponding to an edge
        """
        #super(RauzyGraphShape, self).remove_edge(edge[0],edge[1],key=edge[2]) #oh, the syntax :-D
        
        self.remove_edge(edge[0],edge[1],key=dict_find_key(self.adj[edge[0]][edge[1]],edge[2])) #the key is the real key of some dictionary, not the label...oh...
        del self.__lengths[edge]
        pass

    def incoming_edges_iter(self, node):
        """
        Returns an iterator over incoming edges of a given node.
        """
        for pred in self.predecessors_iter(node) :
            for label in self.get_edge_data(pred, node) :
                yield pred, node, label

    def outgoing_edges_iter(self, node):
        """
        Returns an iterator over outgoing edges of a given node.
        """
        for succ in self.successors_iter(node) :
            for label in self.get_edge_data(node, succ) :
                yield node, succ, label

    def incoming_edges(self, node):
        """
        Returns the list of incoming edges to a node.
        """
        return list(self.incoming_edges_iter(node))

    def outgoing_edges(self, node):
        """
        Returns the list of outgoing edges of a node.
        """
        return list(self.outgoing_edges_iter(node))

    def is_not_special(self,node):
        """
        Tests the speciality of a given node.

        INPUT:
            node - a node in the graph.
        """
        return (self.in_degree(node) == 1) and (self.out_degree(node) == 1)

    def is_strictly_left_special(self, node):
        """
        Tests the strict left speciality of a node (i.e. not bispecial).

        INPUT:
            node - a node in the graph.
        """
        return (self.in_degree(node) > 1) and (self.out_degree(node) == 1)

    def is_left_special(self, node):
        """
        Test the left speciality.

        INPUT:
            node - a node in the graph.
        """
        return (self.in_degree(node) > 1)

    def is_strictly_right_special(self, node):
        """
        Tests the strict right speciality of a given node (i.e. not bispecial).
        """
        return (self.in_degree(node) == 1) and (self.out_degree(node) > 1)
    
    def is_right_special(self, node):
        """
        Tests the right speciality.
        """
        return self.out_degree(node) > 1
    
    def is_not_right_special(self, node):
        """
        
        """
        return self.out_degree(node) == 1

    def is_bispecial(self, node):
        """
        Tests the bispeciality of a node.
        """
        return (self.in_degree(node) > 1) and (self.out_degree(node) > 1)
    
    def is_not_special(self, node):
        """
        Tests the non-speciality of a node.
        """
        return (self.in_degree(node) == 1) and (self.out_degree(node) == 1)

    def bispecials_iter(self):
        """
        Returns an iterator over bispecial vertices.
        """
        for node in self.nodes_iter() :
            if self.is_bispecial(node) : yield node

    def left_specials_iter(self):
        """
        An iterator over LS.
        """
        for node in self.nodes_iter() :
            if self.is_left_special(node) : yield node

    def right_specials_iter(self) :
        """
        An iterator over RS.
        """
        for node in self.nodes_iter() :
            if self.is_right_special(node) : yield node
            
    def not_specials_iter(self) :
        """
        An iterator over not-special nodes.
        """
        for node in self.nodes_iter() :
            if self.is_not_special(node) : yield node

    def bispecials(self) :
        """
        Returns the list of bispecial factors.
        """
        return list(self.bispecials_iter())

    def left_specials(self) :
        """
        Returns the list of left specials factor.
        """
        return list(self.left_specials_iter())

    def right_specials(self) :
        """
        Returns the list of right specials factor.
        """
        return list(self.right_specials_iter())
    
    def not_specials(self) :
        """
        Returns the list of not-specials factor.
        """
        return list(self.not_specials_iter())
    
    def get_length(self,edge):
        """
        Return the length of the corresponding edge.

        INPUT:
            edge - an edge in the graph (a 3-uple)
        """
        return self.__lengths[edge]
    
    def get_length_sum(self): #to be updated by simplex
        for i in self.__lengths: print str(i) + " -> " + str(self.__lengths[i])
        return sum(self.__lengths.values()) #not working well, needs to count in the states
        
    def set_length(self,edge,length):
        """
        Set a new value to the length of the edg in parameter.

        INPUT:
            edge - an edge (a 3-tuple)
            length - the new length
        """
        self.__lengths[edge] = length
    
    def _r_paths_to_next_LS(self, begin, end_node) :
        """
        Must use a special successor function which do not consider 0-state
        edges. Or the treatment can be done after from the reconstitution of the
        paths with edges.

        INPUT :
            begin : a tuple of edges corresponding to the begining of the path.

        OUTPUT :
            tuples : a list of the tuples of edges corresponding to all possible
            ends.
            If no end is possible, the list is empty.
        """
        list_of_ends = []
        outgoing_edges = self.outgoing_edges(end_node)
        #print "begin = ", begin

        for edge in outgoing_edges :
            if edge in begin:
                #print "this edge : ", edge, " is in begin"
                pass

            elif self.is_left_special(edge[1]):
                #print "this edge : ", edge, " is left special"
                
                list_of_ends.append((edge,))                
                
            else:
                #print "this edge : ", edge, " can be continued"
                new_begin = begin + (edge,)
                new_end_node = edge[1]
                #print "the new_begin is : ", new_begin
                new_ends = self._r_paths_to_next_LS(new_begin, new_end_node)
                for end in new_ends :
                    list_of_ends.append((edge,) + end)

        return list_of_ends
        
    def paths_to_next_LS(self, node) :
        """
        Construct all paths starting from node and stopping at the first LS.

            The result is a list of path, and a path is a list of edges.
            Must be left_special inside.
        """
        #list_of_paths = []
        return self._r_paths_to_next_LS((), node)
        
    def _r_paths_to_next_RS(self, begin, end_node) :
        """
        Must use a special successor function which do not consider 0-state
        edges. Or the treatment can be done after from the reconstitution of the
        paths with edges.

        INPUT :
            begin : a tuple of edges corresponding to the begining of the path.

        OUTPUT :
            tuples : a list of the tuples of edges corresponding to all possible
            ends.
            If no end is possible, the list is empty.
        """
        list_of_ends = []
        outgoing_edges = self.outgoing_edges(end_node)
        #print "begin = ", begin

        for edge in outgoing_edges :
            if edge in begin:
                #print "this edge : ", edge, " is in begin"
                pass

            elif self.is_right_special(edge[1]):
                #print "this edge : ", edge, " is left special"
                list_of_ends.append((edge,))

            else:
                #print "this edge : ", edge, " can be continued"
                new_begin = begin + (edge,)
                new_end_node = edge[1]
                #print "the new_begin is : ", new_begin
                new_ends = self._r_paths_to_next_LS(new_begin, new_end_node)
                for end in new_ends :
                    list_of_ends.append((edge,) + end)

        return list_of_ends
        
    def paths_to_next_RS(self, node):
        """
        Return the list of paths from the given node to the next RS.
        """
        return self._r_paths_to_next_RS((), node)

    def is_contractible_edge(self, edge):
        """
        Tests the contractibility of the edge
        """
        return self.is_left_special(edge[0]) and self.is_right_special(edge[1])

    def is_extensible_edge(self, edge):
        """
        Tests the extensibility of the edge
        """
        return self.is_right_special(edge[0]) and self.is_left_special(edge[1])
    
    def contractible_paths_old(self):
        """
        Returns the list of paths that are between a LS and a RS.
        """
        list_of_paths = []
        for node in self.left_specials_iter():
            list_of_paths += self.paths_to_next_RS(node)

        return list_of_paths

    def extensible_paths(self):
        """
        Returns the list of paths that are between a RS and a LS.
        """
        list_of_paths = []
        for node in self.right_specials_iter():
            list_of_paths += self.paths_to_next_LS(node)
        
        return list_of_paths

    def constant_paths(self):
        """
        Returns the list of paths that are between to LS or two RS.
        """
        list_of_paths = []
        for node in self.right_specials_iter() :
            list_of_paths += self.paths_to_next_RS(node)

        for node in self.left_specials_iter() :
            list_of_paths += self.paths_to_next_LS(node)

        return list_of_paths

    def path_to_next_special_old(self, node):
        """
        Returns the name of the node which is the next special node.

            Beware, the algorithm won't stop if there is a loop of non specials
            nodes. Moreover the method will produce an error if there is any
            node without successor ! (Must be fixed)
        """
        path = [node]
        while self.is_not_special(path[-1]):
            successors = self.successors(path[-1])
            if successors == [] :
                raise ValueError, "Your graph as a node without any successor"
            path.append(successors[0])
        return path
    
    def path_to_next_special(self, node):
        """
        Returns path to next special vertex.
        """
        
        visited_nodes = [node]                
        path = []
        
        while self.is_not_special(visited_nodes[-1]):
            
            successors = self.successors(visited_nodes[-1]) #there should be only 1 successor
            
            if successors == [] :
                raise ValueError, "Your graph has a node without any successor"
            
            if visited_nodes.__contains__(successors[0]):
                raise ValueError, "Your graph has a not special loop"
            
            path.append((visited_nodes[-1],successors[0],self[visited_nodes[-1]][successors[0]][0])) #appends the one edge with the right label
            
            visited_nodes.append(successors[0])
        return path  
            
    def path_to_previous_special_old(self, node):
        """
        Returns the name of the node which is the previous special node.

            Beware, the algorithm won't stop if there is a loop of non specials
            nodes. Moreover the method will produce a ValueError if there is any
            node without any predecessor ! (Must be fixed)
        """
        path = [node]
        while self.is_not_special(path[0]):
            predecessors = self.predecessors(path[0])
            if predecessors == []:
                raise ValueError, "Your graph as a node without any predecessor"
            path.insert(0,predecessors[0])
        return path
    
    def path_to_previous_special(self, node):
        """
        Returns the path to the previous special node.
        """
    
        visited_nodes = [node]                
        path = []
        
        while self.is_not_special(visited_nodes[-1]):
            
            predecessors = self.predecessors(visited_nodes[-1]) #there should be only 1 successor
            
            if predecessors == [] :
                raise ValueError, "Your graph has a node without any predecessor"
            
            if visited_nodes.__contains__(predecessors[0]):
                raise ValueError, "Your graph has a not special loop"
            
            path.insert(0,(predecessors[0],visited_nodes[-1],self[predecessors[0]][visited_nodes[-1]][0])) #appends the one edge with the right label
            
            visited_nodes.append(predecessors[0])
        return path


    def regular_paths(self):
        """
        Returns the list of paths existing in the graph that have at least one non special vertice.
        """
        l = self.not_specials()
        list_of_paths = []
        
        while l != []:
            node = l[0]
            
            begin = self.path_to_previous_special(node)
            end = self.path_to_next_special(node)
            
            #for tmp in begin[1:] + end[:-1] :
            #    del l[l.index(tmp)]
                
            #list_of_paths.append(begin + [node] + end) #old version
            list_of_paths.append(begin + end)
            
            for tmp in [begin + end]:
                for ed in tmp[1:]:
                    del l[l.index(ed[0])]
            
        return list_of_paths
            
    def nsegments(self,legacy_tuple = 0):
        """
        Returns the list of nsegments.

            A n-segment is a path from one LS to another not containing a LS and
            without crossing.
        """
        list_of_nsegments = []
        for node in self.left_specials_iter():
            list_of_nsegments += self.paths_to_next_LS(node)
        
        if legacy_tuple == 0:
            l = list_of_nsegments
            list_of_nsegments = []
            while len(l) > 0:
                p = l.pop(0)
                list_of_nsegments.append(list(p))
                    
        return list_of_nsegments
    
    
    def automatic_vertex_rename_old(self):
        """
        Changes the names of all vertices and return the mapping new_name -> old_name.
        """
        
        name_map = {}
        old_map = {}
        
        new_adj = self.adj
        
        i = 1
        
        for key in new_adj.keys():
            name_map[i] = key
            old_map[key] = i
            i = i+1
        
        new_adj = dict_rename_keys(new_adj, old_map)
        
        for key in new_adj.keys():
            new_adj[key] = dict_rename_keys(new_adj[key],old_map)
        
        self.adj = new_adj
        
        return name_map
    
    def automatic_vertex_rename(self):
        """
        Changes the names of all vertices and return the mapping new_name -> old_name.
        """
        
        name_map = {}
        old_map = {}
        
        i = 1
        
        #for key in new_adj.keys():
        for key in self.nodes():
            name_map[i] = key
            old_map[key] = i
            
            self.rename_vertex(key,i)                     
            i = i+1  
        
        return name_map
    
    def rename_vertex(self,old_vertex,new_vertex):
        
        
        self.add_node(new_vertex);
        
        for e in self.incoming_edges(old_vertex):            
            if e[0] == old_vertex:
                self.add_edge(new_vertex, new_vertex, e[2], self.get_length(e))
            else:
                self.add_edge(e[0], new_vertex, e[2], self.get_length(e))
            self.delete_edge_and_length(e)
          
        for e in self.outgoing_edges(old_vertex):
            if e[1] == old_vertex:
                self.add_edge(new_vertex, new_vertex, e[2], self.get_length(e))
            else:
                self.add_edge(new_vertex, e[1], e[2], self.get_length(e))
            self.delete_edge_and_length(e)
        
        
        self.delete_node(old_vertex)
        
        pass
    


class DerivedRauzyGraphShape(RauzyGraphShape):
    """
    Class of derived shape Rauzy Graph.

        The next graph of a given Rauzy Graph is contained in his line Graph (or
        sometimes called derived). This class is intended to share all possibility
        for the choice of the graph inside the derived one.
        One can obtain the next step in selection using the simplify method.

        Implements the states dictionary of potentially removed/added edges.
    """
    def __init__(self, d={}):
        super(DerivedRauzyGraphShape,self).__init__(d)
        # data for mutable edges will be put while deriving here:
        self.__states = {}
        self.__state_lengths = {}
   
    def set_states_from_iterable(self,edges,states):
        """
        Set multiple state from two iterables.
        """
        for edge,state in zip(edges,states) :
            self.set_state(edge,state)

    def get_state(self,edge):
        """
        Returns the state of the specified edge.
        
        INPUT:
            edge -- an edge is a 3-tuple (vertex_from, vertex_to, number)
        """
        if edge not in self.edges():
            if edge not in self.__states:
                raise ValueError, "The edge is not valid"
            else:
                return self.__states[edge]
        return -1
    
    def raw_set_state(self,edge,state):
        """
        Set states without any verification and without modifying the underlying
        graph.

            Do not use if you don't need it.
            
        """
        self.__states[edge] = state
        self.__state_lengths[edge] = self.get_length(edge)
    
    def raw_set_states_from_iterable(self,edges,states):
        """
        Multiple set_states from two iterables.

            Do not use if you don't need it.
        """
        for edge,state in zip(edges,states) :
            self.raw_set_state(edge,state)
    
    def set_state(self,edge,state):
        """
        sets state, only possible from 0<->1
        check strong connectivity
        """
        
        if edge not in self.__states :
            raise ValueError, "This edge is not in the mutable list"

        if state != self.__states[edge] :
            if (state != 0)  and (state != 1) :
                raise ValueError, "The state must be in {0,1}"
            
            if state == 0 :
                self.__states[edge] = 0

                self.delete_edge_and_length(edge)
                
                if not nx.is_strongly_connected(self):
                    self.__states[edge] = 1
                    self.add_edge(edge[0], edge[1], edge[2], self.__state_lengths[edge])
                    return False

            if state == 1 :
                self.__states[edge] = 1
                self.add_edge(edge[0], edge[1], edge[2], self.__state_lengths[edge])
                
        return True

    def mutable_edges_iter(self):
        """
        returns list of edges whose state > -1
        """
        return self.__states.iterkeys()
   
    def mutable_edges(self) :
        """
        Returns the list of mutable_edges.
        """
        return self.__states.keys()
    
    def simplify(self):
        """
        Transforms the derived graph to a graph shape from the actual choice.
        
            The resulting graph has no bispecial vertices at the moment as there may be edges of length 0.
            
            The method deletes the vertices which are not special and keeps the            
            operations in mind and returns it as a dictionary of the form :
               new-edge -> list_of_old_edges (i.e. path)
        """
        G = RauzyGraphShape()
        contracted_edges = {}
        deleted_nodes = self.not_specials()

        l = self.regular_paths()  # the list of paths to contract
        
        for path in l:
            #compute the length and delete edges
            length = 0
                        
            for edge in path:
                length += self.get_length(edge)
                
                self.delete_edge_and_length(edge)

            # add edge and modification of the dictionary
            label = self.add_edge_with_automatic_label(path[0][0],path[-1][1],length)
            contracted_edges[(path[0][0], path[-1][1], label)] = path #new edge -> old path
            
        for node in deleted_nodes :
            self.delete_node(node)

        # the mutation
        del self.__states
        del self.__state_lengths
        self.__class__ = SimplifiedShapeOfRauzyGraph

        return contracted_edges
  

class SimplifiedShapeOfRauzyGraph(RauzyGraphShape):
    """
    Class of simplified shape of Rauzy Graph (sometimes also referred as reduced Rauzy graph).

        A Rauzy graph is simplified if it all its vertices
        are of total valence > 2. In other words, we simply forget all non special vertices
        of a Rauzy graph and we work only with specials.
        
        
    """
    
    
    def contractible_edges(self):
        """
        Returns the list of edges that are from a LS to RS.
        """
        list = []
        for edge in self.edges(data = True):
            if self.is_contractible_edge(edge): list.append(edge)

        return list
    
    def extensible_edges(self):
        """
        Returns the list of edges that are from a RS to LS.
        """
        list = []
        for edge in self.edges(data = True):
            if self.is_extensible_edge(edge): list.append(edge)

        return list
    
    def find_contraction_length(self):
        contractible_edges = self.contractible_edges()
        
        if(len(self.bispecials())) > 0 : #is this needed?
            return 0
        
        if contractible_edges == []:
            raise ValueError, "There are no contractible edges"
        
        min = self.get_length(contractible_edges[0])
        
        for edge in contractible_edges:
            if self.get_length(edge) < min: min = self.get_length(edge) #to be updated by simplex; this comparison will be done by the simplex (one day) and this line will need to modified if the comparison is undecidable
        return min
    
    def execute_length_contraction(self,length):
        """
        Changes lengths: substract from contractibles and adds to extensibles.
        No verification of length argument.
        """
        
        for edge in self.contractible_edges():
            self.set_length(edge,self.get_length(edge) - length) #to be updated by simplex
        for edge in self.extensible_edges():
            self.set_length(edge,self.get_length(edge) + length) #to be updated by simplex
        
        pass
    
    def zero_simplification(self):
        """
        Joins vertices of 0 length into 1 vertex.
        
        This actually gives birth to a bispecial. The name of the vertex is the former LS vertex.
        A dictionary new edge -> old_edges (list) is returned
        
        """
        edges_rename = {}
        
        for edge in self.edges(data=True):
            if self.get_length(edge) == 0: #to be updated by simplex
                for out_edge in self.outgoing_edges(edge[1]):
                    
                    new_label = self.add_edge_with_automatic_label(edge[0], out_edge[1], self.get_length(out_edge))
                    
                    edges_rename[ (edge[0], out_edge[1], new_label) ] = [edge, out_edge]
                
                self.delete_edge_and_length(edge)
                self.remove_node(edge[1])
                
        return edges_rename
        
    
    def contract_edge(self, edge):
        """
        Contract the corresponding edge (which must be contractible !)

        OUTPUT:
            a 4-tuple of dictionnary
              label_changes_start_in : old_label -> new_label
              label_changes_start_out
              label_changes_end_in
              label_changes_end_out
        """
        if not self.is_contractible_edge(edge):
            raise ValueError, "The edge must be contractible"

        label_changes_start_in = {}
        label_changes_start_out = {}
        label_changes_end_in = {}
        label_changes_end_out = {}

        self.add_node(edge)
        self.delete_edge_and_length(edge)

        for old_edge in self.incoming_edges(edge[0]):
            old_label = old_edge[2]
            new_label = self.add_edge_with_automatic_label(
                old_edge[0],
                edge,
                self.get_length(old_edge))
            self.delete_edge_and_length(old_edge)
            label_changes_start_in[old_label] =  new_label

        for old_edge in self.incoming_edges(edge[1]):
            old_label = old_edge[2]
            new_label = self.add_edge_with_automatic_label(
                old_edge[1],
                edge,
                self.get_length(old_edge))
            self.delete_edge_and_length(old_edge)
            label_changes_end_in[old_label] =  new_label

        for old_edge in self.outgoing_edge(edge[0]):
            old_label = old_edge[2]
            new_label = self.add_edge_with_automatic_label(
                edge,
                old_edge[1],
                self.get_length(old_edge))
            self.delete_edge_and_length(old_edge);
            label_changes_start_out[old_label] = new_label

        for old_edge in self.outgoing_edge(edge[1]):
            old_label = old_edge[2]
            new_label = self.add_edge_with_automatic_label(
                edge,
                old_edge[1],
                self.get_length(old_edge))
            self.delete_edge_and_length(old_edge)
            label_changes_end_out[old_label] = new_label


        return label_changes_start_in, label_changes_start_out,
        label_changes_end_in, label_changes_end_out

    # TO FIX : do not return a graph. Change the class. And return a mapping.
    # TO FIX : dependency on labels (it seems that there must not be a gap)
    def derive(self) :
        """
        Return the derived graph.

            The derived graph has edges with special states. Those special
            states are when the edges need not be in the next Rauzy Graph.

            The correspondance dictionnary is naturally obtained from the name
            of the nodes :
              if the node was LS or RS : the new node has the same name
              if the node was BS : the new nodes has name of ancient edges + 'L'
                  or 'R' depending whether the edge is outgoing or incoming.
                  This name is a 4-tuple.

            The multiplicity correspondance of edges is naturally preserved.

        OUTPUT:
            graph - a Derived graph for which some of the edges are mutable.
        """
        H = DerivedRauzyGraphShape({})

        # Bispecial bifurcations 
        for node in self.bispecials_iter():
            for edge_predecessor in self.incoming_edges_iter(node):
                node1 = edge_predecessor + ('E',)
                H.add_node(node1)
                for edge_successor in self.outgoing_edges_iter(node):
                    node2 = edge_successor + ('S',)
                    H.add_node(node2)
                    H.add_edge(node1,node2,0,1)
                    H.raw_set_state((node1,node2,0),1)


        # Edges obtained from the graph
        for edge in self.edges(data=True):
            incr = 0
            if self.is_bispecial(edge[0]):
                node1 = edge + ('S',)
            else:
                node1 = edge[0]
            
            if self.is_left_special(edge[0]):
                incr -= 1
            elif self.is_right_special(edge[0]):
                incr += 1
            else:
                raise ValueError, "The edge %s is not simplified, class SimplifiedShapeOfRauzyGraph cannot contain not special vertices." %(str(edge))

            if self.is_bispecial(edge[1]):
                node2 = edge + ('E',)
            else:
                node2 = edge[1]
                
            if self.is_right_special(edge[1]):
                incr -= 1
            elif self.is_left_special(edge[1]):
                incr += 1
                
            #quickfix - find next free label instead of using edge[2]
            label = 0
            while (node1,node2,label) in self.edges(data=True):
                label = label+1        

            #H.add_edge(node1, node2, edge[2], self.get_length(edge)+incr/2)
            H.add_edge(node1, node2, label, self.get_length(edge)+incr/2)

        return H
    
    
    
    def is_equivalent_with(self,G):
        """
        Tests equivalence with another shape of rauzy graph ...
        
        Say, 2 graphs are equivalent if there exists a vertex bijection and edge bijection between them.
        
        
        Both graphs should be zero-simplified i.e. have no edge of length 0 and have a bispecial factor.
        
        
        0. check if there are length = 0 or no bispecials
        
        1. compare number of vertices and edges
        
        2. compare numbers of specials
        
        3. get the list of bispecials and order it by its order
        
            a. generate pairwise matching function based on the order            
            
            b. start the brutal matching
                
        """


